package pers.sloera.leetcode.editor.cn;

import java.util.HashMap;
import java.util.Map;
import java.util.Optional;
import java.util.regex.Pattern;

/**
 * 字母与数字
 *
 * @author sloera
 * @date 2023-03-11 20:59:25
 */
class FindLongestSubarrayLcci {
    public static void main(String[] args) {
        Solution solution = new FindLongestSubarrayLcci().new Solution();
        // System.out.println(solution.findLongestSubarray( new String[]{"A", "1", "B", "C", "D", "2", "3", "4", "E", "5", "F", "G", "6", "7", "H", "I", "J", "K", "L", "M"}));
        System.out.println(solution.findLongestSubarray(
                new String[]{"42", "10", "O", "t", "y", "p", "g", "B", "96", "H", "5", "v", "P", "52", "25", "96", "b", "L", "Y", "z", "d", "52", "3", "v", "71", "J", "A", "0", "v", "51", "E", "k", "H", "96", "21", "W", "59", "I", "V", "s", "59", "w", "X", "33", "29", "H", "32", "51", "f", "i", "58", "56", "66", "90", "F", "10", "93", "53", "85", "28", "78", "d", "67", "81", "T", "K", "S", "l", "L", "Z", "j", "5", "R", "b", "44", "R", "h", "B", "30", "63", "z", "75", "60", "m", "61", "a", "5", "S", "Z", "D", "2", "A", "W", "k", "84", "44", "96", "96", "y", "M"}));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public final Pattern NUMBER_PATTERN = Pattern.compile("^\\d+$");

        public String[] findLongestSubarray(String[] array) {
            int[] prefixSum = new int[array.length + 1];
            // 记数字加1，字母减1.两个平衡则为0
            for (int i = 0; i < array.length; i++) {
                if (NUMBER_PATTERN.matcher(array[i]).matches()) {
                    prefixSum[i + 1] = prefixSum[i] - 1;
                } else {
                    prefixSum[i + 1] = prefixSum[i] + 1;
                }
            }
            Map<Integer, Integer> maxLengthMinIndexMap = new HashMap<>();
            Map<Integer, Integer> positionMap = new HashMap<>();
            for (int i = 0; i < prefixSum.length; i++) {
                // 上一个相同值的位置，两个的差为0，中间的子数组达到平衡
                if (positionMap.containsKey(prefixSum[i])) {
                    Integer lastIndex = positionMap.get(prefixSum[i]);
                    int length = i - lastIndex;
                    maxLengthMinIndexMap.put(length, Math.min(lastIndex,
                            maxLengthMinIndexMap.getOrDefault(length, Integer.MAX_VALUE)));
                } else {
                    positionMap.put(prefixSum[i], i);
                }
            }
            Optional<Map.Entry<Integer, Integer>> maxOptional = maxLengthMinIndexMap.entrySet().stream()
                    .min((x, y) -> y.getKey().compareTo(x.getKey()));
            if (!maxOptional.isPresent()) {
                return new String[]{};
            }
            Integer maxLength = maxOptional.get().getKey();
            Integer startIndex = maxOptional.get().getValue();
            String[] ret = new String[maxLength];
            System.arraycopy(array, startIndex, ret, 0, maxLength);
            return ret;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}
